package demo31;

public class Test {
    public static void main(String[] args) {
        int[] nums = {1,3,6,2,5,8,1,3,5,3,8,0};
        new Test().quickSortDesc(nums,0,nums.length-1);
        for (int num : nums) {
            System.out.print(num+" ");
        }

    }

    public void nextPermutation(int[] nums) {
        //先检查数组长度
        if(nums.length == 0 || nums.length == 1){
            return;
        }else if(nums.length == 2){
            if (nums[0] < nums[1]){
                int i = nums[0];
                nums[0] = nums[1];
                nums[1] = i;
                return;
            }
            else
            return;
        }
        //循环一遍看看是否存在比num[0]大的数
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] > nums[0]){
                //找到更大的元素，所以选择降序排序(注意，起点下标为1，不为0)
                quickSortDesc(nums,1,nums.length-1);
                return;
            }
        }
        //循环找不到更大的数，选择升序排序
        quickSortAsc(nums,0,nums.length-1);
    }


    //降序快排
    public void quickSortDesc(int[] nums,int start,int end){
        //设置递归头
        if(start >= end){
            return;
        }
        int left = start;
        int right = end;
        int index = start;//设置标志位
        int hole = nums[start];//获取标志元素

        while(left < right){
            //先从右往左扫描
            while(left < right){
                if(nums[right] > hole){
                    //找到比标志元素大的，放左边的坑位，并且在右边挖坑
                    nums[index] = nums[right];
                    index = right;
                    right--;
                    break;
                }
                right--;
            }
            //先从左往右扫描
            while(left < right){
                if(nums[left] < hole){
                    //找到比标志元素小的，放右边的坑位，并且在左边挖坑
                    nums[index] = nums[left];
                    index = left;
                    left++;
                    break;
                }
                left++;
            }
        }
        //将最后一个坑位填上
        nums[index] = hole;
        //递归继续排序
        quickSortDesc(nums,start,index);
        quickSortDesc(nums,index+1,end);
    }



    //升序快排
    public void quickSortAsc(int[] nums,int start,int end){
        //设置递归头
        if(start >= end){
            return;
        }
        int left = start;
        int right = end;
        int index = start;//设置标志位
        int hole = nums[start];//获取标志元素

        while(left < right){
            //先从右往左扫描
            while(left < right){
                if(nums[right] < hole){
                    //找到比标志元素小的，放左边的坑位，并且在右边挖坑
                    nums[index] = nums[right];
                    index = right;
                    right--;
                    break;
                }
                right--;
            }
            //先从左往右扫描
            while(left < right){
                if(nums[left] > hole){
                    //找到比标志元素大的，放右边的坑位，并且在左边挖坑
                    nums[index] = nums[left];
                    index = left;
                    left++;
                    break;
                }
                left++;
            }
        }
        //将最后一个坑位填上
        nums[index] = hole;
        //递归继续排序
        quickSortAsc(nums,start,index);
        quickSortAsc(nums,index+1,end);
    }
}
